Peer-to-peer networks are completely decentralized networks consisting of identical nodes, each of which can act as a “client” (in the sense of a traditional client-server network) and assume the responsibilities of a server at the same time. Because each element of a peer-to-peer (sometimes referred to as “P2P”) network is the same, they are easily scalable. For example, a peer-to-peer network may grow by simply adding more nodes (e.g., telephones, computers, personal digital assistants (“PDAs”)). In addition to being easily scalable it is fairly straightforward to maintain the reliability of peer-to-peer networks.
Typically, nodes or peers within a P2P network monitor each other. If a node or peer fails one or more of the remaining nodes takes over the responsibilities of the failed node. The architectural simplicity of peer-to-peer networks make them attractive for use with certain types of services, such as voice-over-Internet Protocol (“VoIP”). As issues involving the ease of configuring a network and the maintenance costs of a network grow peer-to-peer networks may provide advantages over existing carrier grid networks.
In a conventional peer-to-peer network each node or peer (the two words will be used interchangeably herein) stores attributes known as “key, value” pairs. For example, a key may indicate a user identification (“user ID”) while a value may represent the address of a node. To establish a communication session between a source and destination node in a conventional peer-to-peer network the address of the destination node must be determined by locating a given key,value pair within a node that includes the value (i.e., address) of the destination node using only the key transmitted by the source node. More specifically, each node in the network that receives the transmitted key compares the key to key,value pairs stored in its look-up table or the like. Assuming at least one node contains the key,value pair associated with the destination node, the value (i.e., address) of the destination is returned to the source. Thereafter, the source sets up a signaling path with the destination node. Said another way, if one user wishes to make a VoIP telephone call to another, the caller transmits the intended recipient's user ID to other users (i.e., their devices) in the peer-to-peer network. Using lookup tables and search functions, the address of the recipient is found and returned to the caller to permit the establishment of a signaling path, and eventually a communication session, between the caller and the recipient.
Early peer-to-peer networks “flooded” requests to establish sessions into the entire network or parts of it until the desired key,value pair was identified (i.e., until the address of the recipient of a call was located). However, flooding does not work well in large peer-to-peer networks. To overcome the disadvantages of such a technique, many recent peer-to-peer networks have begun to use distributed hash tables (“DHT”) to store and retrieve key, value pairs.
For example, using DHTs peer-to-peer networks assign a hashed key to each node in the network. By assigning hashed keys to nodes in the network, the time it takes to locate the address of an intended recipient of a call and the like is decreased.
In mathematical terms, it can be said that techniques which use DHTs guarantee an upper bound of O (log N) steps (which corresponds to a time period). In other words, the use of DHTs assures that the maximum number of steps it will take to identify a user (i.e., establish a session) within a peer-to-peer network is O(log N). This provides a way to estimate the time period it will take to locate a recipient's address; a distinct advantage over flooding techniques which, in some cases, would require an indeterminate number of steps or time period to locate a recipient.
Though the use of DHTs provides advantages over earlier techniques, the way they are presently used is still inadequate for use in voice applications/services. More particularly, while present techniques utilizing DHTs provide acceptable time periods to locate a recipient's address for file sharing and other data transfer applications/services, they provide unacceptable time periods when used in voice/video applications. Roughly speaking, using an existing DHT technique it takes an average of 10 steps to find a key, value pair in a network of 1 million nodes. However, in a worst case scenario it may take as many as 20 steps. Using 10 or 20 steps to locate the address of an intended recipient in voice or video applications is undesirable (i.e., it takes too long). Further, as a conventional P2P network gets larger, there also exists the possibility that the number of steps will increase as the number of nodes in the network increases. Thus, while it is still possible to determine the number of steps required to establish a session this number may be too high to provide an acceptable service/application.
Accordingly, it is desirable to provide methods, devices and architectures were DHTs can be used by nodes within a P2P network to establish signaling and communication sessions within an acceptable time period in voice, video and similar applications.